package nfa_generator;

public class NFAGenerator {
	private Object ASTTree;
	private NFAGraph finalGraph;
	private NFAGraph graph1;
	private NFAGraph graph2;
	
	/**
	 * Takes in an AST tree, traverses it, and constructs an NFA graph for the language.
	 * @param ASTTree
	 */
	public static void NFAGenerator(Object ASTTree) {
		//Traverse tree
		//Look for inputs and operations, treat accordingly
		/* http://www.geeksforgeeks.org/archives/618
		Algorithm Postorder(tree)
   		1. Traverse the left subtree, i.e., call Postorder(left-subtree)
   		2. Traverse the right subtree, i.e., call Postorder(right-subtree)
   		3. Visit the root.
   		
   		(ASTTree)
   		Head node (ASTNode)
   		Token Identifier (String)
   		
   		ASTNode:
   		getLeft()
   		getRight()
   		getValue()
   		isOperations()
   		isInput
		 */
		//When tree is fully traversed, return final NFA
		//Generate DFA?
		return;
	}
	
	/**
	 * Builds a primitive, two-node graph for a given input and returns it.
	 * @param input
	 * @return
	 */
	public NFAGraph getPrimitiveGraph(String input) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition(input, endState);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, concatenates them using an epsilon transition, and returns the new graph.
	 * @param g1
	 * @param g2
	 * @return
	 */
	public NFAGraph operatorConcatenation(NFAGraph g1, NFAGraph g2) {
		g1.getEndState().addTransition("epsilon", g2.getStartState());
		NFAGraph newGraph = new NFAGraph(g1.getStartState(), g2.getEndState());
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g2.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in two graphs, ORs them using espison transitions, and returns the new graph.
	 * @param g1
	 * @param g2
	 * @return
	 */
	public NFAGraph operatorAlternation(NFAGraph g1, NFAGraph g2) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		startState.addTransition("epsilon", g2.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		g2.getEndState().addTransition("epsilon", endState);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the replication, or Kleene Enclosure, operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorReplication(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		startState.addTransition("epsilon", endState);
		g1.getEndState().addTransition("epsilon", g1.getStartState());
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the one or more replication operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorReplicationPlus(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		g1.getEndState().addTransition("epsilon", g1.getStartState());
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}
	
	/**
	 * Takes in a graph, applies the zero or one operator using epsilon transitions, and returns the new graph.
	 * @param g1
	 * @return
	 */
	public NFAGraph operatorQuestionMark(NFAGraph g1) {
		NFANode startState = new NFANode();
		NFANode endState = new NFANode();
		startState.addTransition("epsilon", g1.getStartState());
		g1.getEndState().addTransition("epsilon", endState);
		startState.addTransition("epsilon", endState);
		NFAGraph newGraph = new NFAGraph(startState, endState);
		newGraph.addStates(g1.getStates());
		return newGraph;
	}	
}